package com.base.dp;

public class ClimbStairs {

    public static void main(String[] args) {

        ClimbStairs climbStairs = new ClimbStairs();
        System.out.println(climbStairs.climbStairs2(5));
    }

    public int climbStairs3(int n) {
        int[][] q = {{1, 1}, {1, 0}};
        int[][] res = pow(q, n);
        return res[0][0];
    }

    public int[][] pow(int[][] a, int n) {
        //这个是干啥呢
        int[][] ret = {{1, 0}, {0, 1}};
        //次幂
        while (n > 0) {
            //&表示啥意思呢，最后一位二进制是1  这个表示n是单数吧
            if ((n & 1) == 1) {
                //为什么用这个ret数组呢？
                ret = multiply(ret, a);
            }
            //n/2啥意思呢
            n >>= 1;  // n =3 是 n>>=1 n = 1,算一次平方，n就减半，不是-2呢？    算一次平方，就知道多个平方，比如N =8 三次平方就算完了，算一次平方，对平方在平方就算了四次方，以此类推 n 会算logn次
            //
            a = multiply(a, a);
        }
        return ret;
    }

    public int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        //表示几行
        for (int i = 0; i < 2; i++) {
            //表示几列
            for (int j = 0; j < 2; j++) {
                //第i行第一列* 第一例第j行  + 第i行第二列* 第2列第j行
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }

    public int climbStairs2(int n ){
        double sqrt5 = Math.sqrt(5);
        double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
        return (int) Math.round(fibn / sqrt5);

    }
    /**
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * f(x)=f(x−1)+f(x−2)
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        //啥意思，双指针吗？
        int p = 0, q = 0;
        //一个或者两个台阶
        int step = 1;
        //动态规划是啥，台阶如果是1有几种可能，如果是2有几种可能，如果是n有几种可能，
        //动态规划是A(n) 和 A(n-1)之间的关系,f(x)=f(x−1)+f(x−2)
        for (int i = 1; i <= n; i++) {
            //啥意思呢
            p = q;
            //啥意思呢
            q = step;
            //啥意思呢
            step = p + q;
        }
        return step;
    }
}

